package q0005;

import java.util.Arrays;

/**
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author fangjiaxiaobai@163.com
 * @since 2019-06-23
 */
public class Solution2 {

    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int maxCount = 0;
        if (chars.length == 0) {
            return "";
        }

        if (chars.length == 1) {
            return s;
        }
        if (chars.length == 2) {
            if (chars[0] == chars[1]) {
                return s;
            } else {
                return chars[1]+"";
            }
        }
        String content = "";
        for (int i = 0; i < chars.length; i++) {
            int j, k;
            for (j = i - 1, k = i + 1; ; j--, k++) {
                if (k >= chars.length) {
                    break;
                }
                if (j >= 0 && chars[k] == chars[j] && k - j > maxCount) {
                    maxCount = k - j;
                    char[] content1 = Arrays.copyOfRange(chars, j, k + 1);
                    content = new String(content1);
//                        System.out.printf("content=%s   i=%d   j=%d\n", content, i, j);
                } else if (chars[k] == chars[i] && k - i > maxCount) {
                    maxCount = k - i;
                    char[] content1 = Arrays.copyOfRange(chars, i, k + 1);
                    content = new String(content1);
                }
            }
        }
        return content;
    }

    public static void main(String[] args) {
//        test1();
//        System.out.println("-----------------");
//        test2();
//        System.out.println("-----------------");
//        test3();
//        System.out.println("-----------------");
        test4();
//        System.out.println("-----------------");
//        test5();
    }

    private static void test1() {
        String str1 = "babad";
        System.out.printf("%s\n", new Solution2().longestPalindrome(str1));
    }

    private static void test2() {
        String str1 = "babab";
        System.out.printf("%s\n", new Solution2().longestPalindrome(str1));
    }

    private static void test3() {
        String str1 = "cbb";
        System.out.printf("%s\n", new Solution2().longestPalindrome(str1));
    }

    private static void test4() {
        // ffffffffffff
        // dddddddddddd
        String str1 = "cbbdbbddbbbbbbfffffffffffffdddddddddddd";
        System.out.printf("%s\n", new Solution2().longestPalindrome(str1));
    }

    private static void test5() {
        // ffffffffffff
        // dddddddddddd
        String str1 = "ac";
        System.out.printf("%s\n", new Solution2().longestPalindrome(str1));
    }

}
